package com.hanxiaozhang.sort;

import java.util.Arrays;

/**
 * 〈一句话功能简述〉<br>
 * 〈桶排序〉
 *
 * @author hanxinghua
 * @create 2021/9/15
 * @since 1.0.0
 */
public class BucketSort {
    public static void main(String[] args) {


        int[] arr = new int[10];
        arr[0]++;
        System.out.println(arr[0]);

        // Math.pow(x,y) 方法可返回 x 的 y 次幂的值。

        System.out.println((int) Math.pow(2, 3));


        System.out.println("----------------------");

        int[] array = {3, 5, 68, 1, 66, 3, 6, 7};
        countSort(array);
        System.out.println(Arrays.toString(array));


    }

    /**
     * 计数排序
     *
     * @param array
     */
    public static void countSort(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        // 获取最大值
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < array.length; i++) {
            max = Math.max(max, array[i]);
        }
        // 创建一个桶，大小为数组的最大值
        int[] bucket = new int[max + 1];
        // 每个数当做索引，找到桶中位置，桶中相应位置元素+1
        for (int i = 0; i < array.length; i++) {
            bucket[array[i]]++;
        }
        int i = 0;
        // 把桶中信息，再赋值到数组中
        for (int j = 0; j < bucket.length; j++) {
            while (bucket[j]-- > 0) {
                array[i++] = j;
            }
        }
    }



    /**
     * 基数排序
     *
     * @param array
     */
    public static void radixSort(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        radixSort(array, 0, array.length - 1, maxBits(array));
    }


    /**
     * 在array[l..r]范围上排序
     *
     * @param array
     * @param L
     * @param R
     * @param digit 最大值是几位，个位、十位、百位  100 是 3位  10 是 2位
     */
    private static void radixSort(int[] array, int L, int R, int digit) {
        // 都是10的基底
        final int radix = 10;
        int i = 0, j = 0;
        // 有多少个数准备多少个辅助空间
        int[] help = new int[R - L + 1];
        // 有多少位就进出几次
        for (int d = 1; d <= digit; d++) {
            // 10个空间  count[0..9]
            int[] count = new int[radix];
            // 将某位（个位|十位|百位等）的数放入count数字
            for (i = L; i <= R; i++) {
                j = getDigit(array[i], d);
                count[j]++;
            }
            // 将count数组，以此累加 如下：
            // count[0] 当前位(d位)是0的数字有多少个
            // count[1] 当前位(d位)是(0和1)的数字有多少个
            // count[2] 当前位(d位)是(0、1和2)的数字有多少个
            // count[i] 当前位(d位)是(0~i)的数字有多少个
            for (i = 1; i < radix; i++) {
                count[i] = count[i] + count[i - 1];
            }
            // 从array右侧依次获取元素，求某位上的数，
            // 然后根据count位置放入heap数组中，并且 count[j]--
            for (i = R; i >= L; i--) {
                j = getDigit(array[i], d);
                help[count[j] - 1] = array[i];
                count[j]--;
            }
            // 将heap数组导给array数组
            for (i = L, j = 0; i <= R; i++, j++) {
                array[i] = help[j];
            }
        }
    }

    /**
     * 获取数字中，最大数有几位
     *
     * @param array
     * @return
     */
    private static int maxBits(int[] array) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < array.length; i++) {
            max = Math.max(max, array[i]);
        }
        int res = 0;
        while (max != 0) {
            res++;
            max /= 10;
        }
        return res;
    }

    /**
     * 获取数的个位，十位，百位等上的数
     *
     * @param x
     * @param d
     * @return
     */
    public static int getDigit(int x, int d) {
        return ((x / ((int) Math.pow(10, d - 1))) % 10);
    }


}
